/* The dungeon graph is an abstract representation of the dungeon 
 * consisting of segments which are connected through entrances
 * and exits. It is used in the first step of random dungeon generation.
 */
 
#include <string.h>
#include "graph.h"
#include "segments.h"
#include "mt.h"

typedef struct {
	Segment* from;
	int exit;
} Path;

void generate_segment (Segment* s, SegmentType t);
void generate_goal (Segment* s);
void insert_segment (Graph* g, Segment* s, Path (*pop_path) (), void (*push_path) (Path p));
Segment make_support_corridor (int entrances, int exits);

void graph_init (Graph* g, int num_segments)
{
	g->segpool_size = num_segments*2 + MAX(MAX_PATHS, START_PATHS)/MAX_ENTRANCES + 1;
	g->segment_pool = malloc (g->segpool_size * sizeof (Segment));
	g->num_segments = num_segments;
	memset (g->segment_pool, 0, g->segpool_size * sizeof(Segment));
	
	for (int i = 0; i < num_segments; i++)
	{
		generate_segment (&g->segment_pool[i], (mt_rand() % NUM_SEGTYPES) + ST_CORRIDOR);
	}
}

// Future directions for balancing:
// Modify choice of segment; don't just take &segment_pool[next_segment], but qsort
// the segments in the pool according to some balancing criteria. There must not be one
// path with only treasure and another with only monsters.
void graph_connect (Graph* g)
{	
	#define PATH_BUFFER_SIZE (MAX(MAX_PATHS*2,MAX_EXITS*2))
	Path loose_path [PATH_BUFFER_SIZE];
	memset (loose_path, 0, sizeof (loose_path));
	
	for (int i = 0; i < START_PATHS; i++) {
		loose_path[i].from = NULL;
		loose_path[i].exit = i;
	}
	int pathq_begin = 0;
	int pathq_end = START_PATHS;
	int num_stdsegments = g->num_segments;
	
	Path pop_path () { return loose_path [pathq_begin++ % PATH_BUFFER_SIZE]; }
	void push_path (Path p) { loose_path [pathq_end++ % PATH_BUFFER_SIZE] = p; }
	
	for (int next_segment = 0; next_segment < num_stdsegments; next_segment++) {
		insert_segment (g, &g->segment_pool[next_segment], &pop_path, &push_path);
		while ((pathq_end - pathq_begin) < MIN_PATHS) {
			g->segment_pool[g->num_segments] = make_support_corridor (1, MAX_EXITS);
			Segment* s = &g->segment_pool[g->num_segments++];
			insert_segment (g, s, &pop_path, &push_path);
		}
		while ((pathq_end - pathq_begin) > MAX_PATHS) {
			g->segment_pool[g->num_segments] = make_support_corridor (MAX_ENTRANCES, 1);
			Segment* s = &g->segment_pool[g->num_segments++];
			insert_segment (g, s, &pop_path, &push_path);
		}
	}
	
	// Finish with a single exit
	while ((pathq_end - pathq_begin) > 1) {
		int howmany = MIN((pathq_end - pathq_begin),MAX_ENTRANCES);
		g->segment_pool[g->num_segments] = make_support_corridor (howmany, 1);
		Segment* s = &g->segment_pool[g->num_segments++];
		insert_segment (g, s, &pop_path, &push_path);
	}
	assert(g->num_segments < g->segpool_size);
	Segment* goal = &g->segment_pool[g->num_segments++];
	goal->type = ST_GOAL;
	goal->num_entrances = 1;
	goal->num_exits = 0;
	goal->compute_costs_profits = NULL;
	loose_path[pathq_begin % PATH_BUFFER_SIZE].from->num_exits = 1;
	loose_path[pathq_begin % PATH_BUFFER_SIZE].from->next[0] = goal;
	goal->prev[0] = loose_path[pathq_begin % PATH_BUFFER_SIZE].from;
}

Segment make_support_corridor (int entrances, int exits)
{
	Segment s;
	memset (&s, 0, sizeof (Segment));
	generate_segment (&s, ST_MULTIPLEXER);
	s.num_entrances = entrances;
	s.num_exits = exits;
	return s;
}

// Takes some paths from loose_path, sticks them into the segment, 
// and returns the segment exit paths to the loose_path array.
void insert_segment (Graph* g, Segment* s, Path (*pop_path) (), void (*push_path) (Path p))
{	
	for (int entrance = 0; entrance < s->num_entrances; entrance++) {
		Path p = pop_path ();
		s->prev[entrance] = p.from;
		if (p.from != NULL) p.from->next[p.exit] = s;
		else g->next[p.exit] = s;
	}
	
	for (int exit = 0; exit < s->num_exits; exit++) {
		push_path ( (Path) { s, exit } );
	}
}

void graph_cleanup (Graph* g)
{
	free (g->segment_pool);
	memset (g, 0, sizeof(Graph));
}

void find_segment_costs_profits (Segment* from, Segment* to, int* cost, int* profit)
{
	if (from != NULL) {	
		for (int i = 0; i < MAX_EXITS; i++) {
			if (from->next[i] == to) {
				*cost = from->cost[i];
				*profit = from->profit[i];
				return;
			}
		}
	}
		
	*cost = 0;
	*profit = 0;
}

void corridor_costs_profits (Segment* s)
{
	// Costs are min() of all entrances' costs, profits are max() of all entrances' profits 
	int min_cost = 0x7FFFFFFF;
	int max_profit = 0;
	int cost, profit;
	
	for (int i = 0; i < s->num_entrances; i++) {
		find_segment_costs_profits (s->prev[i], s, &cost, &profit);
		min_cost = (cost < min_cost) ? cost : min_cost;
		max_profit = (profit > max_profit) ? profit : max_profit;
	}
	
	for (int i = 0; i < s->num_exits; i++) {
		s->cost[i] = min_cost;
		s->profit[i] = max_profit;
	}
}

void multiplexer_costs_profits (Segment* s)
{
	corridor_costs_profits (s);
}

void shortcut_costs_profits (Segment* s)
{
	corridor_costs_profits (s);
}

void treasure_costs_profits (Segment* s)
{
	corridor_costs_profits (s);
}

void monster_challenge_costs_profits (Segment* s)
{
	corridor_costs_profits (s);
}

void switch_challenge_costs_profits (Segment* s)
{
	corridor_costs_profits (s);
}

void sokoban_challenge_costs_profits (Segment* s)
{
	corridor_costs_profits (s);
}

void multiplayer_challenge_costs_profits (Segment* s)
{
	corridor_costs_profits (s);
}

void generate_corridor (Segment* s)
{
	s->num_entrances = mt_randint(1, MAX_ENTRANCES+1);
	s->num_exits = mt_randint(1, MAX_EXITS+1);
	s->compute_costs_profits = &corridor_costs_profits;
}

void generate_multiplexer (Segment* s)
{
	generate_corridor (s);
	s->compute_costs_profits = &multiplexer_costs_profits;
}

void generate_shortcut (Segment* s)
{
	s->num_entrances = mt_randint(1, MAX_ENTRANCES);
	s->num_exits = mt_randint(1, MAX_EXITS);
	s->compute_costs_profits = &shortcut_costs_profits;
}

void generate_treasure (Segment* s)
{
	generate_corridor (s);
	s->compute_costs_profits = &treasure_costs_profits;
}

void generate_monster_challenge (Segment* s)
{
	generate_corridor (s);
	s->compute_costs_profits = &monster_challenge_costs_profits;
}

void generate_switch_challenge (Segment* s)
{
	generate_corridor (s);
	s->compute_costs_profits = &switch_challenge_costs_profits;
}

void generate_sokoban_challenge (Segment* s)
{
	generate_corridor (s);
	s->compute_costs_profits = &sokoban_challenge_costs_profits;
}

void generate_multiplayer_challenge (Segment* s)
{
	generate_corridor (s);
	s->compute_costs_profits = &multiplayer_challenge_costs_profits;
}

// Generate a segment according to its type
void generate_segment (Segment* s, SegmentType t)
{
	s->type = t;
	
	switch (t) {
	case ST_CORRIDOR: generate_corridor (s); break;
	case ST_MULTIPLEXER: generate_multiplexer (s); break;
	case ST_SHORTCUT: generate_shortcut (s); break;
	case ST_TREASURE: generate_treasure (s); break;
	case ST_MONSTER_CHALLENGE: generate_monster_challenge (s); break;
	case ST_SWITCH_CHALLENGE: generate_switch_challenge (s); break;
	case ST_SOKOBAN_CHALLENGE: generate_sokoban_challenge (s); break;
	case ST_MULTIPLAYER_CHALLENGE: generate_multiplayer_challenge (s); break;
	default: assert(0);
	}
}
